package algorithm.sort;

import java.util.Arrays;

public class radixSort {


    public static void main(String[] args) {
        // 从小到大排序
        System.out.println("======推导========");
        deductionRadix();
        System.out.println("======准备数据========");
        int[] arr = TestHelp.random(10);
        TestHelp.print("比较前",arr);
        long begin = TestHelp.begin();
        radixSort(arr);
        TestHelp.end(begin);
        TestHelp.print("比较后",arr);

    }

    /**
     * 基数排序 确定桶种类，桶的数量，数字的位数有关
     * 时间复杂度O(n+m)
     * 空间复杂度O(n+m)，(k+1)n
     * 稳定,按照顺序进桶，又按照顺序出桶
     * 只适合正数，不适合负数（不建议）
     * 对于int数组来说，一个int有4个字节  4*10*n/1024/1024 二维数组占用的空间，如果需要比较的元素越多，所需要空间越大，越容易堆溢出
     */
    public static void radixSort(int[] arr){
        // 有几位数
        // 找到最大数
        int max=0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>max){
                max = arr[i];
            }
        }
        // 定义桶个数
        // 定义桶里面有几个元素
        int[] bucketSize = new int[10];//0-9 9个桶
        int[][] bucket = new int[10][arr.length];// 10个桶里，最多可以放所有元素

        // 有多少位数，则有多少趟
        int times = (max+"").length();
        for (int t = 0,add=1; t < times; t++,add = add*10) {
            // 先按照个位排序，放进桶里
            for (int i = 0; i < arr.length; i++) {
                // 出取个位,放进相应的桶
                int bucketIndex = arr[i]/add%10;
//                System.out.println("取出的数字："+bucketIndex);
                // 放进相应的桶里
                int size = bucketSize[bucketIndex];
                bucket[bucketIndex][size]=arr[i];
                size++;
                bucketSize[bucketIndex] = size;
            }
            // 将桶中数据按顺序取出，复制到原数组中
            int arrIndex = 0;
            for (int i = 0; i < bucketSize.length; i++) {
                if(bucketSize[i] > 0){
                    for (int j = 0; j < bucketSize[i]; j++) {
                        int element = bucket[i][j];
                        arr[arrIndex] = element;
                        arrIndex++;
                    }
                }
                // 清空桶里面记录的数量，供下一趟使用
                bucketSize[i] = 0;
            }
            TestHelp.print("第"+t+"趟",arr);
        }

    }



    /**
     * 逐步推导，演绎
     */
    public static void deductionRadix(){
        int[] arr = new int[]{8,3,12,6,19,2,33,111,2,5};
        // 有几位数
        // 找到最大数
        int maxIndex = 0;
        int max=0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>max){
                max = arr[i];
                maxIndex = i;
            }
        }
        // 第一趟
        // 定义桶个数
        // 定义桶里面有几个元素
        int[] bucketSize = new int[10];//0-9 9个桶
        int[][] bucket = new int[10][arr.length];// 10个桶里，最多可以放所有元素
        // 先按照个位排序，放进桶里
        for (int i = 0; i < arr.length; i++) {
            // 出取个位,放进相应的桶
            int bucketIndex = arr[i]/1%10;
            System.out.println("取出的数字："+bucketIndex);
            // 放进相应的桶里
            int size = bucketSize[bucketIndex];
            bucket[bucketIndex][size]=arr[i];
            size++;
            bucketSize[bucketIndex] = size;
        }
        // 将桶中数据按顺序取出，复制到原数组中
        int arrIndex = 0;
        for (int i = 0; i < bucketSize.length; i++) {
            if(bucketSize[i] > 0){
                for (int j = 0; j < bucketSize[i]; j++) {
                    int element = bucket[i][j];
                    arr[arrIndex] = element;
                    arrIndex++;
                }
            }
            // 清空桶里面记录的数量，供下一趟使用
            bucketSize[i] = 0;
        }
        TestHelp.print("第一趟",arr);
        // 第二趟 =====================
        for (int i = 0; i < arr.length; i++) {
            // 出取十位,放进相应的桶
            int bucketIndex = arr[i]/10%10;
            System.out.println("取出的数字："+bucketIndex);
            // 放进相应的桶里
            int size = bucketSize[bucketIndex];
            bucket[bucketIndex][size]=arr[i];
            size++;
            bucketSize[bucketIndex] = size;
        }
        // 将桶中数据按顺序取出，复制到原数组中
        arrIndex = 0;
        for (int i = 0; i < bucketSize.length; i++) {
            if(bucketSize[i] > 0){
                for (int j = 0; j < bucketSize[i]; j++) {
                    int element = bucket[i][j];
                    arr[arrIndex] = element;
                    arrIndex++;
                }
            }
            // 清空桶里面记录的数量，供下一趟使用
            bucketSize[i] = 0;
        }
        TestHelp.print("第二趟",arr);
        // 第三趟 =====================
        for (int i = 0; i < arr.length; i++) {
            // 出取百位,放进相应的桶
            int bucketIndex = arr[i]/100%10;
            System.out.println("取出的数字："+bucketIndex);
            // 放进相应的桶里
            int size = bucketSize[bucketIndex];
            bucket[bucketIndex][size]=arr[i];
            size++;
            bucketSize[bucketIndex] = size;
        }
        // 将桶中数据按顺序取出，复制到原数组中
        arrIndex = 0;
        for (int i = 0; i < bucketSize.length; i++) {
            if(bucketSize[i] > 0){
                for (int j = 0; j < bucketSize[i]; j++) {
                    int element = bucket[i][j];
                    arr[arrIndex] = element;
                    arrIndex++;
                }
            }
            // 清空桶里面记录的数量，供下一趟使用
            bucketSize[i] = 0;
        }
        TestHelp.print("第三趟",arr);
    }


}
